//给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 
//
// 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。 
//
// 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
// 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：3 
//解释：12 = 4 + 4 + 4 
//
// 示例 2： 
//
// 
//输入：n = 13
//输出：2
//解释：13 = 4 + 9 
// 
//
// 提示： 
//
// 
// 1 <= n <= 104 
// 
// Related Topics 广度优先搜索 数学 动态规划 
// 👍 1147 👎 0

package com.cute.leetcode.editor.cn;

import java.util.*;

public class PerfectSquares {
    public static void main(String[] args) {
        System.out.println(new PerfectSquares().new Solution().dpNumSquares(12));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 我居然还真整出来了，使用的BFS的思想
         * 队列存储数组，第一位存储的是个数，第二个存储的是剩余的值
         * 剩余值为0的话返回步数就行了
         * 添加第一层的时候为了防止成环进行了一下判断
         */
        public int numSquares(int n) {
            Set<Integer> set = new HashSet<>();
            if (((int)Math.sqrt(n))*((int)Math.sqrt(n)) == n) return 1;
            Queue<int[]> queue = new LinkedList<>();
            for (int i = n-1; i >0 ; i--) {
                ///添加比n小的所有的平方数，避免重复添加而造成环
                if (((int)Math.sqrt(i))*((int)Math.sqrt(i)) == i){
                    if (!set.contains(n-i)){
                        //这里第一个位置添加的是步数，第二个位置添加的是剩余值
                        queue.add(new int[]{1,n - i});
                        set.add(n-i);
                    }
                }
            }
            while (!queue.isEmpty()){//遍历所有的值
                int[] temp = queue.poll();
                if (temp[1] == 0) {
                    return temp[0];
                }
                for (int i = temp[1]; i >0 ; i--) {
                    //添加比当前剩余值小的所有平方数，仍然避免成环（因为前边大的时候已经包含了一部分情况了）
                    if (((int)Math.sqrt(i))*((int)Math.sqrt(i)) == i){
                        if (temp[1]-i<=i)
                            queue.add(new int[]{temp[0]+1,temp[1] - i});
                    }
                }
            }
            return -1;
        }
        /**
         * 动态规划
         */
        public int dpNumSquares(int n) {
            int[] dp = new int[n + 1]; // 默认初始化值都为0
            for (int i = 1; i <= n; i++) {
                dp[i] = i; // 最坏的情况就是每次都只能+1，所以先赋值为i到最大值
                for (int j = 1; i - j * j >= 0; j++) {//这里是小范围遍历
                    //比如说i=5，那么5的最小次数是dp[4]或dp[1] 中+1 与5比较的最小值
                    //5的时候没必要看3和2中的结果了，3 2根本就不是平方数
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
                }
            }
            return dp[n];
        }

        //二刷的时候，先获取了小于n的所有平方数，再遍历的，这样居然比之前的一维dp还要快
        //时间复杂度为n
        public int numSquaresTwo(int n) {
            int[] nums = getNums(n);
            int[] dp = new int[n+1];
            Arrays.fill(dp,n+1);
            dp[0] = 0;
            for (int num : nums){
                for (int i = num; i <= n; i++){
                    dp[i] = Math.min(dp[i],dp[i-num]+1);
                }
            }
            return dp[n];
        }
        public int[] getNums(int n){
            List<Integer> list = new ArrayList<>();
            for (int i = 1; i<=n; i++)
                //这里必须强转为int，否则会出错
                if ((int) Math.sqrt(i) * (int) Math.sqrt(i) == i) list.add(i);
            return list.stream().mapToInt(Integer::valueOf).toArray();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}